package kr.ac.ssu.ailab.Control;

import java.awt.Point;
import java.util.Vector;
import kr.ac.ssu.ailab.Model.Data.Cell;
import kr.ac.ssu.ailab.View.SeqTest;

/**
 * Thread 로 구현된 Heuristic PathFininding 을 하는 Class
 * 
 * @author Neil
 * 
 */
public class HeuristicPathFinding implements Runnable
{
	public final int TEST_TIME = 10;

	public final int NO_PATH = -1;
	public final int NOT_FOUND = 0;
	public final int FOUND = 1;
	public final int FINISH_STATE = 2;
	public final int SHOW = 3;

	private Thread loop;
	private Vector<Cell> openList = null;
	private Vector<Cell> closedList = null;
	private static int leng;
	private int level;

	private Cell finish = null;
	private Cell first = null;

	private static Vector<Cell> goalList;
	private static Vector<Cell> pathList;
	private boolean match = false;
	private boolean finalState = false;

	public static int stepSpeed = 100;

	/**
	 * 생성자
	 */
	@SuppressWarnings("unchecked")
	public HeuristicPathFinding()
	{
		loop = new Thread(this);
		openList = new Vector<Cell>();
		closedList = new Vector<Cell>();
		goalList = new Vector<Cell>();
		pathList = new Vector();
	}

	/**
	 * Thread Loop 를 get 하는 method
	 * 
	 * @return
	 */
	public Thread getLoop()
	{
		return loop;
	}

	/**
	 * Thread Loop 를 Set 하는 method
	 * 
	 * @param loop
	 */
	public void setLoop(Thread loop)
	{
		this.loop = loop;
	}

	/**
	 *Heuristic 을 이용한 Search 를 시작하는 method
	 */
	public void startSearch()
	{
		openList = new Vector<Cell>();
		closedList = new Vector<Cell>();
		pathList = new Vector();
		this.loop.start();
	}

	@Override
	public void run()
	{
		int max = 0;
		int count = 0;
		int state = NOT_FOUND;
		double searchTime = 0;

		openList.addElement(SeqTest.mapControl.getStartCell());
		while (state == NOT_FOUND)
		{
			state = stepLv1();

			try
			{
				loop.sleep(stepSpeed);
			}
			catch (InterruptedException e)
			{
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		/* Show optimized path if being found */
		if (state == FOUND)
		{

			setPathLv1();

		}
		else
		{
			System.out.println("No Path Found");
			loop.interrupt();
		}
		// System.out.println(" Search Count : " + openListCount);

		move();

	}

	/**
	 * A* algorithm �� �⺻������ �˻��ܰ� method
	 * 
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public int step()
	{
		int tests = 0;
		boolean found = false;
		first = SeqTest.mapControl.getStartCell();
		finish = SeqTest.mapControl.getFinishCell();

		Vector<Cell> temp = (Vector<Cell>) openList.clone();
		// find the most promising edge cell
		double min = Double.MAX_VALUE;
		double score;

		// int best = -1;
		Cell best = (Cell) temp.elementAt(temp.size() - 1);
		Cell now;

		for (int i = 0; i < temp.size(); i++)
		{
			now = (Cell) temp.elementAt(i);
			if (!closedList.contains(now))
			{
				score = now.getDistFromStart();
				// System.out.println("score = " 8+ score);
				score += now.getWeight();
				score += now.getDistFromFinish();

				if (score < min)
				{
					min = score;
					best = now;
				}
			}
		}
		now = best;

		openList.removeElement(now);
		closedList.addElement(now);

		// if (now.getType() == CellControl.NORMAL || now.getType() ==
		// CellControl.OPENLIST ||
		// now.getType() == CellControl.HARD)
		now.setType(CellControl.CLOSEDLIST);

		/* next 8 Cell around current cell */
		Cell next[] = SeqTest.mapControl.getAdjacentCell(now);
		int length = next.length;
		for (int i = 0; i < length; i++)
		{
			if (next[i] != null)
			{
				if (next[i] == finish)
				{
					found = true;
				}
				// if (next[i].getType() != CellControl.OBSTACLE)
				if (!next[i].isObstacle())
				{
					next[i].setParentPoint(now.getPosition());
					next[i].setDistFromStart(now.getDistFromStart() + 1);
					next[i].setDistFromFinish(tie_breaking_Heuristic(next[i], finish, 1));

					// next[i].setDistFromFinish(cbDistTest3(next[i], finish,
					// 1));
					if (!openList.contains(next[i]) && !closedList.contains(next[i]))
					{
						openList.addElement(next[i]);

						// if (next[i].getType() == CellControl.NORMAL)
						{
							next[i].setType(CellControl.OPENLIST);

						}
					}
				}
			}
			if (found)
			{
				System.err.println("Found goal at " + finish.getPosition());
				return FOUND;
			}
		}

		if (openList.size() == 0)
		{
			return NO_PATH;
		}
		// now process best.
		return NOT_FOUND;
	}

	
	/**
	 * Path 를 찾은후에 Path 에 대한 경로를 Set 하는 method 
	 */
	public void setPath()
	{
		boolean finished = false;

		Cell next;

		Cell stop = SeqTest.mapControl.getStartCell();
		Cell now = SeqTest.mapControl.getFinishCell();

		Vector<Cell> tempList = new Vector<Cell>();

		while (!finished)
		{

			next = SeqTest.mapControl.getLowestAdjacent(now);
			now = next;
			CellControl.setCellType(now, CellControl.PART_OF_PATH);
			tempList.addElement(now);

			if (now == stop)
			{
				System.out.println("Path Found");
				finished = true;
			}
		}
		sortOfPathList(tempList);
	}

	/**
	 * Path List 를 재정렬 하는 메소드
	 * @param tempList
	 */
	private void sortOfPathList(Vector<Cell> tempList)
	{

		for (int i = tempList.size() - 1; i >= 0; i--)
		{
			pathList.add(tempList.get(i));
		}

	}

	
	/**
	 * Lv1 Graph 의 중간경로가 결정되어지고 난후에 그래프의 랠리 포인트를 따라서 찾아가는 method
	 * @return
	 */
	public int stepLv1()
	{

		boolean found = false;
	
		openList.addElement(first);

		

		Vector<Cell> temp = (Vector<Cell>) openList.clone();
	
		double min = Double.MAX_VALUE;
		double score;

		// int best = -1;
		Cell best = (Cell) temp.elementAt(temp.size() - 1);
		Cell now;

		for (int i = 0; i < temp.size(); i++)
		{
			now = (Cell) temp.elementAt(i);
			if (!closedList.contains(now))
			{
				score = now.getDistFromStart();
				score += now.getWeight();
				score += now.getDistFromFinish();

				if (score < min)
				{
					min = score;
					best = now;
				}
			}
		}
		now = best;
		openList.removeElement(now);
		closedList.addElement(now);

		if (now.getType() == CellControl.NORMAL || now.getType() == CellControl.OPENLIST
				|| now.getType() == CellControl.HARD)
			now.setType(CellControl.CLOSEDLIST);

		/* next 8 Cell around current cell */

		Cell next[] = SeqTest.mapControl.getAdjacentLv1Cell(now, match);
		int length = next.length;
		for (int i = 0; i < length; i++)
		{
			if (next[i] != null)
			{
				if (next[i] == finish)
				{
					found = true;
				}
				// if (next[i].getType() != CellControl.OBSTACLE)
				if (!next[i].isObstacle())
				{
					next[i].setParentPoint(now.getPosition());
					next[i].setDistFromStart(now.getDistFromStart() + 1);
					next[i].setDistFromFinish(tie_breaking_Heuristic(next[i], finish, 1));
					if (!openList.contains(next[i]) && !closedList.contains(next[i]))
					{
						openList.addElement(next[i]);
						next[i].setType(CellControl.OPENLIST);
					}
				}
			}

			if (found)
			{
				System.err.println("Found goal at " + finish.getPosition());
				return FOUND;
			}
		}

		if (openList.size() == 0)
		{
			return NO_PATH;
		}

		return NOT_FOUND;
	}


	/**
	 * Lv1 Graph 를 이용하여 찾은 경로를 Set하는 method 
	 */
	public void setPathLv1()
	{
		boolean finished = false;

		Cell next;

		Cell stop = first;
		Cell now = finish;
		// first, finish

		// Vector<Cell> tempList = new Vector<Cell>();

		while (!finished)
		{
			if (now == SeqTest.mapControl.getFinishCell())
			{
				// System.out.println("finalstate");
				finalState = true;
			}
			next = SeqTest.mapControl.getCellArray()[now.getParentPoint().x][now.getParentPoint().y];

			now = next;
			CellControl.setCellType(now, CellControl.PART_OF_PATH);
		
			if (now == stop)
			{
				System.out.println("Path Found");
				finished = true;
			}
		}

	}

	/**
	 *  결정되어진 경로를 가지고 실제로 move 하는 메소드 
	 */
	private void move()
	{
		while (pathList.size() != 0)
		{
			try
			{
				loop.sleep(20);
				// pathList.firstElement().setType(Color.black);
				// pathList.firstElement().repaint();
				// UnitControl.moveUnit(pathList.firstElement());
				pathList.removeElement(pathList.firstElement());

			}
			catch (InterruptedException e)
			{
				e.printStackTrace();
			}
		}
	}

	/**
	 * AStar 를 이용할때 사용하는  Heuristic (diagonal 방식)
	 * 
	 * @param nodeA
	 * @param nodeB
	 * @param low
	 * @return
	 */
	public static double calDist(Cell nodeA, Cell nodeB, double low)
	{
		int nodeAX = nodeA.getPosition().x;
		int nodeAY = nodeA.getPosition().y;
		int nodeBX = nodeB.getPosition().x;
		int nodeBY = nodeB.getPosition().y;

		double h_diagonal = Math.min(Math.abs(nodeAX - nodeBX), Math.abs(nodeAY - nodeBY));
		double h_straight = ((Math.abs(nodeAX - nodeBX) + Math.abs(nodeAY - nodeBY)));
		double result = (low * Math.sqrt(2)) * h_diagonal + low * (h_straight - 2 * h_diagonal);
		// System.out.println("Cost : " + result);
		return result;
	}

	/**
	 * AStar 를 이용할때 사용하는  Heuristic (tie_breaking 방식)
	 * 
	 * @param nodeA
	 * @param nodeB
	 * @param low
	 * @return
	 */
	public static double tie_breaking_Heuristic(Cell nodeA, Cell nodeB, double low)
	{
		int nodeAX = nodeA.getPosition().x;
		int nodeAY = nodeA.getPosition().y;
		int nodeBX = nodeB.getPosition().x;
		int nodeBY = nodeB.getPosition().y;
		Point start = SeqTest.mapControl.getStartCell().getPosition();

		double dx1 = nodeAX - nodeBX;
		double dy1 = nodeAY - nodeBY;
		double dx2 = start.x - nodeBX;
		double dy2 = start.y - nodeBY;
		double cross = dx1 * dy2 - dx2 * dy1;
		if (cross < 0)
			cross = -cross; // absolute value

		/**/
		return (low * (Math.abs(dx1) + Math.abs(dy1) + cross * 0.0002)) * 2;

	}

	/**
	 *  AStar 를 이용할때 사용하는  Heuristic ( manhattan 방식)
	 * 
	 * @param nodeA
	 * @param nodeB
	 * @param low
	 * @return
	 */
	public static double manhattan(Cell nodeA, Cell nodeB, double low) // Manhattan
	// Distance
	{
		int nodeAX = nodeA.getPosition().x;
		int nodeAY = nodeA.getPosition().y;
		int nodeBX = nodeB.getPosition().x;
		int nodeBY = nodeB.getPosition().y;
		// (abs(n.x-goal.x) + abs(n.y-goal.y))

		double h_straight = ((Math.abs(nodeAX - nodeBX) + Math.abs(nodeAY - nodeBY)));
		double result = +low * h_straight;
		return result;
		// return low * (Math.abs(a.x - b.x) + Math.abs(a.y - b.y) - 1);
	}

}
